The present invention relates to public-key encryption systems, which employ the RSA so-called "trap-door, one-way permutation" data encryption. More particularly, the present invention relates to the method and apparatus employing a currently commercially available microprocessor for generating the large random prime numbers satisfying the requirements for the so-called "trap-door, one-way permutation," incorporated into an RSA public-key data encryption system.
Public-key data encryption, as originally suggested by Diffie and Hellman, "New Directions In Cryptography," I.E.E.E. Transactions on Information Theory (November 1976) (the disclosure of which is hereby incorporated by reference), and perfected by Rivest, Shamir, and Adelman, "A Method for Obtaining Digital Signatures in Public-Key Crypto Systems," MIT Technical Memo LCS/TM82 (August 1977) (the disclosure of which is hereby incorporated by reference), is by now well-known. The basic reason for public-key encryption system is to ensure both the security of the information transferred along a data line, and to guarantee the identity of the transmitter and ensure the inability of a receiver to "forge" a transmission as being one from a subscriber on the data line. Both of these desired results can be accomplished with public-key data encryption without the need for the maintenance of a list of secret keys specific to each subscriber on the data line and/or the periodic physical delivery or otherwise secure transmission of secret keys to the various subscribers on the data line. Through the use of the so-called "open trap-door, one-way permutations" data can be sent from a transmitter to a receiver in an encrypted form using a publicly-known publicly transmitted encryption key, but at the same time not allowing an eavesdropper on the line to be able to decrypt the message within a period of time so large as to guarantee the security of the encrypted message.
This method of public-key encryption developed by Rivest, Shamir & Adelman, and now generally referred to as RSA, is based upon the use of two extremely large prime numbers which fulfill the criteria for the "trap-door, one-way permutation." Such a permutation function enables the sender to encrypt the message using a non-secret encryption key, but does not permit an eavesdropper to decrypt the message by crypto-analytic techniques within an acceptably long period of time. This is due to the fact that for a composite number composed of the product of two very large prime numbers, the computational time necessary to factor this composite number is unacceptably long. Another method of public-key encryption has been suggested for the transmittal of NBS standard keys in "Electronics" magazine of June 5, 1980 at 96-97. This does not use the RSA scheme, but rather employs a public key encryption scheme similar to earlier proposals by, e.g., Hellman, prior to RSA, and has certain security problems not associated with the RSA scheme.
Generally, the RSA system has the following features. Assuming that the receiver of the message is located at terminal A, terminal A will have first computed two very large random prime numbers p, q. The product of p and q is then computed and constitutes the value n. A large random integer e is then selected which has the property that the greatest common divisor of e and the product of (p-1) and (q-1) is 1, i.e., EQU GCD[e,(p-1)(q-1)]=1
In other words, e is a large random integer which is relatively prime to the product of (p-1) and (q-1). An integer d is then computed which is the "multiplicative inverse" of e in modulo (p-1) (q-1). That is to say: EQU e*d.ident.1[mod(p-1)(q-1)].
Terminal A transmits n and e to another terminal, Terminal B, in plain text without encryption, or a public list of n and e for every terminal, including Terminal A, is made publicly known. Terminal B responds to encrypting and transmitting a message M into an encrypted transmission C as follows: EQU C.ident.E(M).ident.M.sup.e (mod n).
It will be understood that each character transmitted along the data network is encoded as a number prior to any encryption, and upon decryption the identical number will result which corresponds to the identical character.
It will be further understood that the message M to be encrypted may be a single binary number of, e.g., 25 bytes in length, i.e., 336 bits, with each group of, e.g., 3 or 4 bits representing the encoding of a specific character within the message M. When the encrypted message C is received and decrypted using the RSA scheme, the identical 25 byte binary number is reproduced, from which the encoded data characters of the message M can be decoded as is well in the art.
Terminal B then sends the encrypted message C. Terminal A then performs an operation upon the received encoded message C as follows: EQU (C).sup.d (mod n)
Due to the particular nature of the selected large random prime numbers this "open trap-door, one-way permutation" results in the identical message M.
However, an eavesdropper on the line who receives or otherwise knows the publicly transmitted n and e cannot decode the message sent by terminal B without the number d. Thus, the transmission from Terminal B to Terminal A, after receipt of or knowledge of at Terminal B of n and e computed at or for Terminal A, is totally secure. In addition, because the sender of the message and the intended receiver of the message each have a unique n and e, the sender and receiver can each guarantee the authentication of the other by an encrypted "signature", encrypted using their separate n's and e's and decrypted using their separate d's. In this way, both sender and receiver can guarantee the authentication of the origin and receipt of the particular message. This is extremely important in applications such as encrypted electronic mail used for business transactions where proof of transmission and receipt are vital.
In the past, however, the use of such an RSA public-key encryption system has been limited to transmitting and receiving terminals which have access to large scale digital data computers. This is due to the fact that the generation of the required large random prime numbers has only been practical on large scale digital computers. This is because the random numbers p and q must be extremely large. For example, as explained in Rivest, Shamir & Adelman in the above-noted technical memo, there exists a factoring algorithm, the Schroeppel algorithm, for factoring a number n. For a n of e.g., 50 digits in length, the Schroeppel algorithm can be used to factor n in 3.9 hours, on a large scale digital computer. Factoring n is the easiest technique for use by a cryptoanalyst to break the RSA encryption code. If the length of n is increased to 100 digits, the computational time necessary for complete factoring with the Schroeppel algorithm increases to 73 years. Approximately a 1,000 year period is generally accepted as being a totally secure computational decryption time for an encrypted message. This requires a n of approximately 120 digits in length. Since n is derived from the product of two large prime numbers p and q, the product of p and q will have a number of digits equal to the sum of the digits in p and q. Therefore, p and q must be large random prime numbers each having approximately 60 digits in order for about a 1,000 year cryptoanalysis time using, e.g., the Schroeppel algorithm. A good rule of thumb is that for each 2.5 digits in a decimal number there will be one byte of eight binary bits, thus sixty digits would translate to 24 bytes.
The method of finding large random primes outlined in the RSA scheme requires the evaluation of a.sup.P-1 (mod P) for 100 random a&lt;P. If for any a, a.sup.P-1 (mod P) is not 1, then another P must be chosen and another iteration of 100 modulo exponentiations begun. For the processing of a digital binary representation of decimal numbers on a commercially available microprocessor, each exponentiation requires a multi-precision multiply and divide for each bit in the exponent and an additional multiply and divide for each 1 bit. Thus, for each p and q, which must be on the order of about 184 bits (23 bytes) in order for the product p.times.q to be of the required approximately 50 bytes in length, each exponentiation takes an average of 92 seconds on a microprocessor, for example, an Intel 8085 microprocessor.
In testing the RSA scheme, it has been found that most of the time, whenever 3.sup.P-1 (mod P) is 1, then a.sup.P-1 (mod P) is also 1 for each choice of o&lt;a&lt;P. Therefore, the first value of a was always chosen to be 3, and the remaining 99 were chosen as random. Approximately 120 value P have to be tested before one is found which works. The time to find such a P using commercially available microprocessors averages approximately 3 hours. Since 4 separate primes are required for RSA implementation, 12 hours are needed to find the 4 prime numbers with a probability of 1/2. For the recommended probability of 2.sup.-100, the time necessary increases to 1200 hours.
Public-key encryption has tremendous utility in both unique signatures for message authentication and for transmitting on open channels the periodic changes in encryption keys, e.g., the NBS standard keys. In the latter application, the need for a master key in which to encrypt the periodic changes of the standard key is avoided. Thus, the need to transmit over a secure channel or to physically transport the master key by courier or the like is avoided. Without public-key encryption, each subscriber must have the master key. Though the master key does not change often, as each new subscriber comes on the data encryption line, a master key must be sent in some secure manner to that subscriber. Each such transfer, even over a secure channel or by physical hand delivery, could be compromised, thus necessitating changing the master key for all subscribers, when and if compromise is discovered, and putting the master key in the hands of each subscriber in a secure manner. Public-key encryption enables the standard keys, which change periodically, to be sent over open channels to each subscriber with a publicly-known public-key, which though publicly known, is not capable of decryption by anyone other than the individual subscriber. The utility of a public-key data encryption system for message authentication and transmission of standard keys is more fully described in Hellman, "The Mathematics of Public-Key Cryptography," Scientific American, Vol. 241 (1979), the disclosure of which is hereby incorporated by reference.
These advantages of public-key encryption will enable the expanded use of encryption using, e.g., the NBS standard keys, for message transfers by electronic means in business applications, where security and transmission and receipt authentication are crucial. Presently, however, in order to come "on-line" in such a data encryption system, using RSA public-key encryption for the transfer and receipt of the standard keys, or signatures, a large start-up time or access to a large-scale digital computer is needed. Another alternative of hand delivery of the large randomly generated prime numbers, unique to each subscriber, exists. However, this also requires a possibly compromisable physical transfer by some secure means, which cannot always be guaranteed secure. This also requires the same central location which generates and provides the "secret" public-key decryption key also, at least at some time prior to providing this decryption key to a subscriber, know this key. This is another possible avenue of compromise.
It is, therefore, much more preferable for each subscriber to be able to generate its own large randomly selected prime numbers. Currently, in order to do this, access to a large-scale digital computer is needed, or some twelve to twenty hours of computational time, on a currently commercially available microprocessor, is needed. Even with twelve to twenty hours on the microprocessor, using the exponentiation technique suggested by Rivest, Shamir and Adelman, the numbers generated have only a 50% probability of being prime. The only way to check the primality is to try encrypting and decrypting a message using the generated primes in the RSA scheme. For the recommended probability of 2.sup.-100, 1200 hours of computation time, approximately, are needed on currently commercially available microprocessors.
There thus exists a tremendous need for an RSA public-key data encryption system in which a subscriber, having only a microprocessor of the kind currently commercially available, can come on-line in a relatively short period of time by generating the required prime numbers in a few hours, rather than dozens of hours.
The use of a GCD routine according to the present invention for eliminating composite numbers without exponentiation, along with a unique method of forming a sequence of primes, enables this time to be decreased to about 2 hours, because the number of required exponentiations is dropped from 120 to 20 for each P tested. And only 2 are needed as opposed to standard RSA's 4 (see line 30, page 5). In addition, because the sequence of primes is generated in the form of (hP+1), finding an hP+1 which is prime and of a sufficient length as one of the RSA large random prime numbers p or q, the value of p-1 (or q-1), i.e, hP, will also have a large prime factor, satisfying the RSA requirements. Thus, only hP+1 must be tested for primality, eliminating one of the required tests of primality in the RSA scheme for each of p and q. Therefore, two large random numbers of the form hP+1 must be tested for primality according to the present invention, rather than four numbers according to the suggested procedure in the RSA scheme. The GCD routine eliminates most non-primes. The GCD routine involves the use of a pre-computed composite number equal to the product of the first selected number, e.g., 34 of the known prime numbers, i.e., less than or equal to 139, in a determination of whether the GCD of that composite number and the number being tested is equal to 1. The GCD equaling 1 is a necessary but not sufficient test of the primality of the number being tested. Thus, if the GCD does not equal 1, then the number can be eliminated as a choice of a prime number without the need for the further tests for primality. The further tests for primality according to the present invention are the Euler identities, which constitute a determination of whether both of the following relationships hold true: EQU 2.sup.hP .ident.1(mod hP+1) EQU 2.sup.h .notident.1(mod hP+1)
The reason that most non-primes are found by the GCD routine is that a random sample of odd integers has 1/3 of the integers divisable by 3, 1/5th by 5, etc. Tests by the applicants have shown that about 140 hP+1 random numbers of 23 bytes long must be chosen in accordance with the present invention before a prime number is found. Using a sample of the size of 140, 1/139 or 1 of the sample numbers should be divisible by 139, which is the largest prime not greater than 140. If the sample number is divisible by any of the primes of up to 139, then a composite number which has that prime as a factor will have a GCD with respect to the sample number that is not equal to 1. By using a composite number equal to the product of all of the 34 primes up to 139, the GCD test checks whether the sample is divisible by one of those primes.
The present invention relates, therefore, to a method and apparatus employing a commercially available microprocessor for selecting the large random prime numbers necessary for RSA public-key encryption. More particularly, the present invention relates to a large prime number generating system for use in a public-key encryption system to determine the large random prime numbers by generating a sequence of prime numbers hP+1, where P initially is a randomly selected known prime number of a short length relative to the approximately 23 byte size of the desired randomly selected prime number, and wherein the successive numbers in the sequence have the relationship of hP+1 to the preceding prime number P in the sequence, with h initially being selected to be of a byte length approximately 1/2 that of the byte length of P, and the values of hP+1 being initially checked by the GCD routine to eliminate the necessity of checking the number hP+1 with the exponentiation modulo (hP+1) tests of primality for a large number of the value of n=hP+1, as h is incremented to h+2 until the value of n is determined to be prime for a given n in the sequence.
The unique method and apparatus employing the GCD elimination along with the generation of a sequence of primes hP+1 until a prime of sufficient length is reached, which prime hP+1 is also in the precise form needed for RSA public-key encryption, and is guaranteed to be a prime, rather than probabilistically selected as prime as with pure exponentiation prime derivation, makes the generation of prime numbers of suitable length on a microprocessor commercially feasible for RSA systems.
The problems enumerated in the foregoing are not intended to be exhaustive, but are rather among many which tend to impair the effectiveness of previously-known methods and apparatus for generating large random prime numbers for use in RSA public-key encryption. Other noteworthy problems may also exist; however, those presented above should be sufficient to demonstrate methods and apparatus for generating random prime numbers for RSA public-key encryption appearing in prior art have not been altogether satisfactory.
Examples of the more important features of the present invention have been summarized broadly in order that the detailed description thereof that follows may be better understood, and in order that the contribution to the art may be better appreciated. There are, of course, features of the invention that will be described hereinafter and which will also form the subject of the appended claims. These other features and advantages of the present invention will become more apparent with reference to the following detailed description of a preferred embodiment thereof in connection with the accompanying drawings, in which: